﻿#pragma once
#include "Index.h"
#include "NumMatrix.h"

/**
 * 矩阵区域和
 * 题目:https://leetcode.cn/problems/matrix-block-sum/
 * 题解:https://leetcode.cn/problems/matrix-block-sum/solution/ju-zhen-qu-yu-he-by-leetcode-solution/
 * 数组 矩阵 前缀和
 *
 * 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，
 * 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 
 * i - k <= r <= i + k,
 * j - k <= c <= j + k 且
 * (r, c) 在矩阵内。
 */
class NumMatrixExtendSum {
public:
	std::vector<std::vector<int>> matrixBlockSum(std::vector<std::vector<int>>& mat, int k)
	{
		const int row = mat.size();
		const int col = row > 0 ? mat.front().size() : 0;
		if (row == 0 || col == 0 || k <= 0)
			return {};

		NumMatrix numMat;
		numMat.initRegion(mat);

		std::vector<std::vector<int>> ans;
		ans.resize(row, std::vector<int>(col, 0));
		for (int i = 0; i < row; ++i)
			for (int j = 0; j < col; ++j)
			{
				const int row0 = std::max<>(0, i - k);
				const int col0 = std::max<>(0, j - k);
				const int row1 = std::min<>(row - 1, i + k);
				const int col1 = std::min<>(col - 1, j + k);

				ans[i][j] = numMat.sumRegion(row0, col0, row1, col1);
			}
		return ans;
	}
};